package com.hyb.algorithm.data.struct.dp;

import java.util.Arrays;
import java.util.Comparator;

/**
 * @author: ybhu
 * @create: 2021/08/30 23:00
 * <p>
 * 435. 无重叠区间
 * <p>
 * https://leetcode-cn.com/problems/non-overlapping-intervals/
 */
public class EraseOverlapIntervals {

    public static void main(String[] args) {

    }

    /**
     * 输入: [ [1,2], [2,3], [3,4], [1,3] ]
     * <p>
     * 输出: 1
     * <p>
     * 解释: 移除 [1,3] 后，剩下的区间没有重叠。
     *
     * @param intervals
     * @return
     */
    public int eraseOverlapIntervals(int[][] intervals) {

        if (intervals.length <= 0) {
            return 0;
        }

        // 按 end 升序排序
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] a, int[] b) {
                return a[1] - b[1];
            }
        });

        //至少有一个不重叠
        int count = 1;
        // 排序后，第一个区间就是 x
        int currentEnd = intervals[0][1];

        for (int[] arr : intervals) {
            int start = arr[0];
            if (start >= currentEnd) {
                // 找到下一个选择的区间了
                count++;
                currentEnd = arr[1];
            }
        }

        return count;

    }
}
